#include "string_array.h"

using namespace std;

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout<<"   "<<this->length;
    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}


/*************************STRING*****************************/
//其他可以考虑的构造函数
//myStr(const int&);
//myStr(const myStr&);
myStr::myStr(const char* S){
    if (S == nullptr)
    {
        data = nullptr;
        length = 0;
        next = nullptr;
        nextVal = nullptr;
    }else {
        int l = 0;
        while (S[l] != '\0')
        {
            l ++;
        }
        data = new char[l + 1];
        for (int i = 0; i < l; i++)
        {
           data[i] = S[i];
        }
        data[l] = '\0';
        length = l;
        next = new int[length];
        nextVal = new int[length];
        this->kmp_next();
        this->kmp_nextVal();
    }
}

myStr::~myStr(){
    if (data != nullptr) {
        delete[] data;
    }
    if (next != nullptr) {
        delete[] next;
    }
    if (nextVal != nullptr) {
        delete[] nextVal;
    }
}


void myStr::kmp_next(){
    // next[0] = -1;
    // int i = 0, j = -1;
    // while (i < length) {
    //     cout<<data[i];
    //     if (j == -1 || data[i] == data[j]) {
    //         i++;
    //         j++;
    //         next[i] = j;
    //     } else {
    //         j = next[j];
    //     }
    // }
    next[0] = 0;
    int i = 1, j = 0;
    while (i < length) {
        if (j == 0 || data[i - 1] == data[j - 1]) {
            i++;
            j++;
            next[i - 1] = j;
        } else {
            j = next[j - 1];
        }
    }
}

void myStr::kmp_nextVal(){
    // nextVal[0] = -1;
    // int i = 0, j = -1;
    // while (i <= length) {
    //     if (j == -1 || data[i] == data[j]) {
    //         i++;
    //         j++;
    //         if (data[i] != data[j]) {
    //             nextVal[i] = j;
    //         } else {
    //             nextVal[i] = nextVal[j];
    //         }
    //     } else {
    //         j = next[j];
    //     }
    // }
    nextVal[0] = 0;
    int i = 1, j = 0;
    while (i < length) {
        if (j == 0 || data[i - 1] == data[j - 1]) {
            i++;
            j++;
            if (data[i - 1] != data[j - 1]) {
                nextVal[i - 1] = j;
            } else {
                nextVal[i - 1] = nextVal[j - 1];
            }
        } else {
            j = next[j - 1];
        }
    }
}


    
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V){
    if (start <= 0 || start > S.length || T.length == 0)return false;

    int sLen = S.length;
    int tLen = T.length;
    int vLen = V.length;

    int findIdx = -1;
    for (int i = start - 1; i <= sLen - tLen; i++)
    {
        int j;
        for (j = 0; j < tLen; j++)
        {
            // cout<<S.data[i + j]<<"-"<<T.data[j]<<endl;
            if (S.data[i + j] != T.data[j])
            {
                break;
            }
        }
        if (j == tLen)
        {
            findIdx = i;
            break;
        }
    }
    if (findIdx == -1)
    {
        return false;
    }
    
    S.length = sLen - tLen + vLen;
    char* tmp = new char[S.length + 1];
    for (int i = 0; i < findIdx; i++)
    {
        tmp[i] = S.data[i];
        // cout<<tmp[i]<<"-";
    }
    for (int i = findIdx; i < findIdx + vLen; i++)
    {
        tmp[i] = V.data[i - findIdx];
        // cout<<tmp[i]<<"-";
    }
    for (int i = findIdx; i + tLen < sLen; i++)
    {
        tmp[i + vLen] = S.data[i + tLen];
        // cout<<tmp[i + vLen]<<"-";
    }
    tmp[S.length + 1] = '\0';
    S.data = tmp;
    S.kmp_next();
    S.kmp_nextVal();
    return findIdx != -1;
}

int kmpMatch(const myStr& S, const myStr& T){
    int i = -1, j = -1;
    int sLen = S.length, tLen = T.length;
    while (i < sLen && j < tLen)
    {
        if (j == -1 || S.data[i] == T.data[j])
        {
            i++;
            j++;
        }else{
            j = T.nextVal[j] - 1;
        }
    }
    if (j >= tLen)
    {
        return i - tLen + 1;
    }
    return -1;
}

int simpleMatch(const myStr& S, const myStr& T){
    int slen = S.length, tlen = T.length;
    for (int i = 0; i <= slen - tlen; i++)
    {
        int j;
        for (j = 0; j < tlen; j++)
        {
            if (S.data[i + j] != T.data[j])
            {
                break;
            }
            
        }
        if (j == tlen)
        {
            return i + 1;
        }
    }
    
    return -1;
}


/*****************************MATRIX**********************************/
//建议加入的构造函数
//myMatrix();
//myMatrix(const myMatrix&);
myMatrix::myMatrix(){}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* t){
    this->colNum = cNum;
    this->rowNum = rNum;
    this->nodeNum = nNum;
    this->nodeList = new matrixNode[nodeNum];

    int *num = new int[rNum + 1];
    int *cpot = new int[rNum + 1];
    for (int i = 0; i <= rNum; i++)
    {
        num[i] = 0;
    }

    for (int i = 0; i < nodeNum; i++)
    {
        ++num[t[i*3]];
    }
    cpot[1] =1;
    for (int i = 2; i <= rNum; i++)
    {
        cpot[i] = cpot[i-1] + num[i - 1];
    }
    
    for (int i = 0; i < nodeNum; i++)
    {
        int q = cpot[t[i*3]];
        this->nodeList[q - 1] = matrixNode{t[i*3], t[i*3 + 1], t[i*3 + 2]};
        ++cpot[t[i*3]];
    }
    
    for (int i = 0; i < nodeNum; i++)
    {
        for (int j = 0; j < nodeNum - i - 1; j++)
        {
            if (this->nodeList[j].row == this->nodeList[j + 1].row)
            {
                if (this->nodeList[j].col > this->nodeList[j + 1].col)
                {
                    //交换两个三元组
                    int tmpcol = this->nodeList[j].col;
                    int tmpval = this->nodeList[j].value;
                    this->nodeList[j].col = this->nodeList[j + 1].col;
                    this->nodeList[j].value = this->nodeList[j + 1].value;
                    this->nodeList[j + 1].col = tmpcol;
                    this->nodeList[j + 1].value = tmpval; 
                }
                
            }
            
        }
        
    }
    
    
    
}

myMatrix::~myMatrix(){
    
}

void myMatrix::FastTransposeSMatrix(myMatrix& T){
    int mc = this->colNum;
    int mr = this->rowNum;
    int mn = this->nodeNum;
    T.colNum = mr;
    T.nodeNum = mn;
    T.rowNum = mc;
    T.nodeList = new matrixNode[mn];
    int *num = new int[mc + 1];
    int *cpot = new int[mc + 1];
    if (mn != 0)
    {
        // 初始化每列非零元素的个数数组
        for (int i = 1; i <= mc; i++)
        {
            num[i] = 0;
        }

        for (int i = 0; i < mn; i++)
        {
            ++num[this->nodeList[i].col];
        }
        // 初始化每列非零元素的第一个位置的数组
        cpot[1] =1;
        for (int i = 2; i <= mc; i++)
        {
            cpot[i] = cpot[i - 1] + num[i - 1];
        }
        
        for (int i = 0; i < mn; i++)
        {
            int c = this->nodeList[i].col;
            int r = this->nodeList[i].row;
            int v = this->nodeList[i].value;
            // cout<<r<<"-"<<c<<"-"<<v<<endl;
            int q = cpot[c];
            T.nodeList[q - 1] = matrixNode{c, r, v};
            ++cpot[c];
        }
        
    }
    
}